#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
  // result[i] = result[i]
  /*
    right[i] indice [0->i] mutiply
    left[j] indice [j->n] mutiply
    result[i] = left[i-1] *right[i+1]
   */
  vector<int> productExceptSelf(vector<int> &nums) {
    int length = nums.size();

    vector<int> result(length, 0);
    vector<int> left(length, 0);
    vector<int> right(length, 0);

    left[0] = nums[0];
    for (int i = 1; i < length; i++) {
      left[i] = left[i - 1] * nums[i];
    }

    right[length - 1] = nums[length - 1];
    for (int i = length - 2; i >= 0; i--) {
      right[i] = right[i + 1] * nums[i];
    }

    result[0] = right[1];
    result[length - 1] = left[length - 2];
    for (int i = 1; i < length - 1; i++) {
      result[i] = left[i - 1] * right[i + 1];
    }

    return result;
  }
};

int main() { return 0; }
